1279B - Verse For Santa - CodeForces Solution


binary search brute force implementation *1300

Please click on ads to support us..

Python Code:

import sys,bisect
input=lambda:sys.stdin.readline().rstrip()
def solve():
	N,S=map(int,input().split())
	A=list(map(int,input().split()))
	B=[0 for i in range(N+1)]
	for i in range(1,N+1):
		B[i]=A[i-1]+B[i-1]
	ans=bisect.bisect_left(B,S+1)-1
	ret=0
	for i in range(1,N+1):
		if B[i-1]>=S:
			break
		if ans<bisect.bisect_left(B,S+A[i-1]+1)-2:
			ans=bisect.bisect_left(B,S+A[i-1]+1)-2
			ret=i
	print(ret)
T=int(input())
for i in range(T):
	solve()

C++ Code:

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define END return 0;
#define yes cout << "YES" << '\n';
#define no cout << "NO" << '\n';
#define endl '\n'

void Fast() {
    cin.tie(0), cout.tie(0), cin.sync_with_stdio(0), cout.sync_with_stdio(0);
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
}

void test_case() {
    ll n,s;cin>>n>>s;
    vector<ll>v(n);
    for (int i = 0; i < n; ++i) {
        cin>>v[i];
    }
    for (int i = 1; i < n; ++i) {
        v[i]=v[i]+v[i-1];
    }
    int mxlen=0,ind=-1,len;
    for (int i = -1; i < n; ++i) {
        if(i==0)
            len=upper_bound(v.begin(),v.end(),s+(v[i]))-v.begin();
        else if (i==-1)
            len=upper_bound(v.begin(),v.end(),s)-v.begin();
        else
            len=upper_bound(v.begin(),v.end(),s+(v[i]-v[i-1]))-v.begin();
        if(len>mxlen&&i<len){
            ind=i;
            mxlen=len;
        }
    }
    cout<<ind+1<<endl;
}

int main()
{
    Fast();
    int T = 1;
    cin >> T;
    while (T--)
        test_case();
    END
}


Comments

Submit
0 Comments
More Questions

479C - Exams
1030A - In Search of an Easy Problem
158A - Next Round
71A - Way Too Long Words
160A - Twins
1A - Theatre Square
1614B - Divan and a New Project
791A - Bear and Big Brother
1452A - Robot Program
344A - Magnets
96A - Football
702B - Powers of Two
1036A - Function Height
443A - Anton and Letters
1478B - Nezzar and Lucky Number
228A - Is your horseshoe on the other hoof
122A - Lucky Division
1611C - Polycarp Recovers the Permutation
432A - Choosing Teams
758A - Holiday Of Equality
1650C - Weight of the System of Nested Segments
1097A - Gennady and a Card Game
248A - Cupboards
1641A - Great Sequence
1537A - Arithmetic Array
1370A - Maximum GCD
149A - Business trip
34A - Reconnaissance 2
59A - Word
462B - Appleman and Card Game